//https://leetcode.cn/problems/01-matrix/submissions/589247437/
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int numr = matrix.size();
        int numc = matrix[0].size();
        vector<pair<int, int>> around = { {0,1},{0,-1},{-1,0},{1,0} };
        vector<vector<int>> result(numr, vector<int>(numc, INT_MAX));
        queue<pair<int, int>> que;
        for (int i = 0; i < numr; i++) {
            for (int j = 0; j < numc; j++) {
                if (matrix[i][j] == 0) {
                    result[i][j] = 0;
                    que.push({ i, j });
                }
            }
        }
        while (!que.empty()) {
            auto temp = que.front();
            que.pop();
            for (int i = 0; i < 4; i++) {
                int x = temp.first + around[i].first;
                int y = temp.second + around[i].second;
                if (x >= 0 && x < numr && y >= 0 && y < numc) {
                    if (result[x][y] > result[temp.first][temp.second] + 1) {
                        result[x][y] = result[temp.first][temp.second] + 1;
                        que.push({ x, y });
                    }
                }

            }
        }
        return result;
    }
};
